<html>
<head><meta charset="utf-8"><title>proc macro trie construction · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html">proc macro trie construction</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="203884737"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203884737" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Benedikt Mandelkow <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203884737">(Jul 14 2020 at 20:37)</a>:</h4>
<p>Hello, I have been thinking about constructing (String) tries at compile time and attempted it in zig <a href="https://gist.github.com/benmkw/4c3d04ec87dd7668e4af972d5ae6971b">https://gist.github.com/benmkw/4c3d04ec87dd7668e4af972d5ae6971b</a> and there is prior work in cpp e.g. <a href="https://github.com/smilingthax/cttrie">https://github.com/smilingthax/cttrie</a>. I could not find something that does the same in rust. If it isn just me searching in all the wrong places and also not a limitation of proc macros (I don't think it should be a limitation because I think I can sort tokens and output some if statements?) then this might be an interesting project to learn more about proc macros. Thanks for your thoughts!</p>



<a name="203889004"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203889004" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203889004">(Jul 14 2020 at 21:12)</a>:</h4>
<p>yeah you should be able to</p>



<a name="203889792"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203889792" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Benedikt Mandelkow <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203889792">(Jul 14 2020 at 21:19)</a>:</h4>
<p>ok nice, this will make it harder to give up once I try :)</p>



<a name="203890177"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203890177" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203890177">(Jul 14 2020 at 21:22)</a>:</h4>
<p>you probably want a hierarchy of <code>match</code>es so it compiles down like a <code>switch</code> would in other languages</p>



<a name="203890252"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203890252" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203890252">(Jul 14 2020 at 21:23)</a>:</h4>
<p>you might even get away without a hierarchy, and just expanding <code>"foo"</code> into <code>[b'f', b'o', b'o']</code>, depending on how the pattern-matching compiles that</p>



<a name="203940988"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203940988" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Benedikt Mandelkow <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203940988">(Jul 15 2020 at 11:04)</a>:</h4>
<p>It would certainly be interesting to compare it against the match approach. I would expect the match to do comparisons for each char and not reuse them across branches (like reuse the prefixes) but I'd like to be wrong on that.</p>



<a name="203941045"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203941045" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203941045">(Jul 15 2020 at 11:05)</a>:</h4>
<p><span class="user-mention" data-user-id="309872">@Benedikt Mandelkow</span> it will not reuse anything if you use <code>"..."</code> literals as patterns. it does something more advanced, IIRC, when there is some structure to the pattern</p>



<a name="203941175"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203941175" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203941175">(Jul 15 2020 at 11:07)</a>:</h4>
<p>in some cases <code>match x { pat0 =&gt; ..., pat1 =&gt; ..., ... }</code> might be similar to <code>if let pat0 = x { ... } else if let pat1 = x { ... } else ...</code></p>



<a name="203941217"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203941217" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203941217">(Jul 15 2020 at 11:07)</a>:</h4>
<p>but I believe we still try to do better than that when there's some prefix sharing in the patterns. cc <span class="user-mention" data-user-id="116009">@nikomatsakis</span> <span class="user-mention" data-user-id="116118">@Matthew Jasper</span></p>



<a name="203942426"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203942426" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Benedikt Mandelkow <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203942426">(Jul 15 2020 at 11:22)</a>:</h4>
<p>ok so its probably also a question if this happens when matching on str as well which would make this whole DIY approach redundant for that case. And maybe this happens for small matches by llvm but not for longer ones so its a question of who does it? </p>
<p>If it happens for matches on slices (and not just by llvm) but not for str, a manual implementation might still make sense. <br>
But I was just curious about proc macros so its not primarily a discussion about performance for me because there are obviously other options like perfect hashing available as well so I kind of expect matches to not use such a specific technique (trie) by default.</p>



<a name="203942440"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203942440" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203942440">(Jul 15 2020 at 11:22)</a>:</h4>
<p>it doesn't for (byte) string literals</p>



<a name="203942452"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203942452" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203942452">(Jul 15 2020 at 11:23)</a>:</h4>
<p>for various reasons we just <code>memcmp</code> in that case</p>



<a name="203946202"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/203946202" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Matthew Jasper <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#203946202">(Jul 15 2020 at 12:05)</a>:</h4>
<p>We do better in cases like: <code>Some(1) =&gt; { ... }, Some(2) =&gt; { ... }</code> (we only check the enum discriminant once).</p>



<a name="209218884"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/proc%20macro%20trie%20construction/near/209218884" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Benedikt Mandelkow <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/proc.20macro.20trie.20construction.html#209218884">(Sep 06 2020 at 10:18)</a>:</h4>
<p>I can show some results <a href="https://paste.rs/Lls">https://paste.rs/Lls</a> <br>
notably the unsafe version trusts the input to be one of the enum variants <br>
don't really have a conclusion but it was fun and maybe I can turn this into a proper api/ have some ideas left and will show up again then :D</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>